The present disclosure relates to networking technologies, and more particularly to techniques for performing efficient multicast operations.
Multicast routing protocols are used to distribute data to multiple recipients. IP multicasting enables a sender device (or sender host) to send a packet to a set of recipients. The set of recipients is referred to as a multicast group and is represented by an IP address referred to as the multicast address. A multicast address thus corresponds to or represents a group of IP hosts that have joined the multicast group and want to receive packets whose destination address is the multicast address. By specifying a multicast address as the destination address for a packet (referred to as a multicast packet or multicast IP datagram), the packet is then delivered to the zero or more members (receivers) of the multicast group.
The membership of a multicast group is dynamic—hosts may join and leave multicast groups at any time. There is typically no restriction on the location or number of members in a multicast group. An IP host may be a member of more than one multicast group at a time. A host need not be a member of a group to be able to send multicast packets. Internet Group Management Protocol (IGMP) is an example of a protocol that facilitates formation and management of multicast groups. Hosts may use IGMP to join or leave multicast groups. Hosts may also use IGMP to advertise their membership in a multicast group.
Forwarding of multicast packets from senders to receivers is performed by a fabric of network devices (e.g., routers, switches) that execute a multicast routing protocol. For example, multicast routing may be performed using Protocol Independent Multicast (PIM), which is a collection of multicast routing protocols including protocols such as PIM Sparse-Mode, PIM dense Mode, Bi-directional PIM, and others. PIM and its variants provide a set of protocols that can be used by network devices such as routers providing multicast routing services to distribute information about multicast group membership.
Network devices such as routers that are configured to perform multicast routing are also referred to as multicast routers. A multicast router typically maintains multicast state information (also referred to as multicast information) that is used by the router to forward a multicast packet to its multicast group receivers. The multicast information can include PIM mcache information (also referred to as a multicast routing table) with multiple forwarding entries (referred to as mcache entries) that are cached by the router and are used to determine how a multicast packet is to be forwarded by the router.
For some networks, there may be tens of thousands of mcache entries. PIM mcache information is conventionally structured with hash tables and linked lists, such that all mcache entries that hash to the same hash bucket is further organized as a linked list. Because of this structure, with conventional multicast routing techniques, when an event occurs (e.g., a link goes down), all of the mcache entries need to be traversed to determine which particular mcache entries are affected by the event. This need to traverse all mcache entries can lead to significant inefficiency if the number of mcache entries affected is very small relative to the number of entries.